LC 315. Count of Smaller Numbers After Self

Posted on | In |

Description

You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i].

Example:
Input: [5,2,6,1]
Output: [2,1,1,0]
Explanation:
To the right of 5 there are 2 smaller elements (2 and 1).
To the right of 2 there is only 1 smaller element (1).
To the right of 6 there is 1 smaller element (1).
To the right of 1 there is 0 smaller element.

Solution

Solution 1(merge sort, O(nlogn))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution:
    def countSmaller(self, nums: List[int]) -> List[int]:
        # merge sort solution
        def mergeSort(l, r): # ordinary mergeSort, time complexity: O(nlogn)
            if l >= r: return
            m = (r - l) // 2 + l
            mergeSort(l, m)
            mergeSort(m + 1, r)
            merge(l, m, m + 1, r)

        def merge(l1, r1, l2, r2):
            '''
            Attention: nums[l1 : r1 + 1] and nums[l2 : r2 + 1] are sorted, therefore, the cnt should be increasing as nums[l1 : r1 + 1] is increasing
            Also, as we will change the idx array to track the original index, nums[idx[i]] is increasing
            '''
            nonlocal idx, res
            start = l1
            tep = [0] * (r2 - l1 + 1)
            p = 0
            cnt = 0
            while l1 <= r1 or l2 <= r2:
                if l1 > r1:
                    tep[p] = idx[l2]
                    l2 += 1
                elif l2 > r2:
                    res[idx[l1]] += cnt
                    tep[p] = idx[l1]
                    l1 += 1
                elif nums[idx[l1]] <= nums[idx[l2]]:
                    res[idx[l1]] += cnt
                    tep[p] = idx[l1]
                    l1 += 1
                else:
                    cnt += 1
                    tep[p] = idx[l2]
                    l2 += 1
                p += 1
            for i in range(0, p):
                idx[i + start] = tep[i]

        n = len(nums)
        idx = list(range(n))
        res = [0] * n
        mergeSort(0, n - 1)
        return res

Solution 2(bst, O(n ^ 2) in worst case)

https://leetcode.com/problems/count-of-smaller-numbers-after-self/discuss/76580/9ms-short-Java-BST-solution-get-answer-when-building-BST

Donate comment here